In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Każda bramka XOR ma dwa wejścia i jedno wyjście, a jej działanie opisuje następująca tabelka:
wejście 1 wejście 2 wyjście 0 0 0 0 1 1 1 0 1 1 1 0
Siecią XOR nazywamy układ bramek XOR, mający wejść i jedno wyjście, spełniający następujące warunki:
Przedstawiony na rysunku układ bramek mający wejść i wyjście spełnia warunki 1–5, więc jest siecią XOR. Uwaga: bramki na rysunku zostały ponumerowane dowolnie, ale istnieje numeracja spełniająca warunek określony w punkcie 5.
Wszystkie wejścia sieci są ponumerowane od do . Stan wejść sieci XOR opisuje słowo wejściowe utworzone z cyfr dwójkowych i — przyjmujemy, że -ta od lewej cyfra danego słowa wejściowego, to stan -tego wejścia sieci. Dla dowolnego stanu wejść sieć daje na wyjściu albo . Każde słowo wejściowe jest dwójkowym zapisem jakiejś liczby naturalnej, więc słowa te można uporządkować zgodnie z ich wartościami liczbowymi. Sieci XOR będziemy testowali podając na wejściu kolejne słowa z ustalonego zakresu i zliczając liczbę otrzymanych w wyniku jedynek.
Napisz program, który:
Zakładamy, że: , oraz, że bramki danej sieci są ponumerowane w dowolnym porządku liczbami od do .
W pierwszym wierszu standardowego wejścia są zapisane trzy liczby całkowite dodatnie pooddzielane pojedynczym odstępem. Jest to liczba wejść danej sieci XOR, liczba bramek oraz numer bramki połączonej z wyjściem sieci.
W kolejnych wierszach znajdują się opisy połączeń bramek sieci. W -tym z tych wierszy, dla od do , znajduje się opis połączeń dwóch wejść bramki o numerze , który ma postać dwóch liczb całkowitych nie mniejszych niż i nie większych niż , oddzielonych pojedynczym odstępem. Jeśli odpowiednie wejście do bramki jest połączone z wejściem do sieci o numerze , to opisem tego połączenia jest liczba ujemna , a jeśli wejście do bramki jest połączone z wyjściem innej bramki o numerze , to opisem tego połączenia jest liczba dodatnia .
W kolejnych dwóch wierszach są zapisane dwa -bitowe słowa oraz . Jest to dolne i górne ograniczenie zakresu testowania sieci. Zakładamy, że w danym zakresie mieści się nie więcej niż słów.
Na standardowe wyjście należy zapisać jedną liczbę całkowitą nieujemną — liczbę jedynek, jakie powinniśmy otrzymać na wyjściu poprawnie działającej danej sieci XOR dla słów wejściowych z danego zakresu: , gdzie nierówność należy rozumieć jako relację porządku zgodnego z wartościami liczbowymi słów dwójkowych.
Dla danych wejściowych:
5 6 5 -1 -2 1 3 1 -2 2 -3 4 6 -4 -5 00111 01110
poprawną odpowiedzią jest:
5
Autor zadania: Tomasz Śmigielski.